package JoReg

func (this *NfaManager) match(str string) []string {
	if str == "" {
		return nil
	}
	accessibleSet := make(map[*Nfa]struct{})
	accessibleSet[this.startNfaPtr] = struct{}{}
	// 空边集合
	eClosureSet := this.eClosure(accessibleSet)

	charSlc := []byte(str)
	matchSlc := make([]string, 0)
	validStr := ""
	acceptFlag := false
	for i, char := range charSlc {
		// 匹配字符的可达集合
		accessibleSet = this.move(eClosureSet, char)
		// 可达状态的空边集合
		eClosureSet = this.eClosure(accessibleSet)
		// 判断是否有可接受状态
		if this.hasAcceptState(eClosureSet) {
			acceptFlag = true
		}
		if len(accessibleSet) > 0 {
			validStr += string(char)
			if i+1 >= len(charSlc) && acceptFlag {
				// 已经匹配到结尾并且有接受状态
				matchSlc = append(matchSlc, validStr)
				validStr = ""
			}
		} else {
			if acceptFlag {
				// 由可达转为不可达并且有接受状态
				matchSlc = append(matchSlc, validStr)
				validStr = ""
			}
			acceptFlag = false
			// 后续的字符重新匹配
			accessibleSet = make(map[*Nfa]struct{})
			accessibleSet[this.startNfaPtr] = struct{}{}
			eClosureSet = this.eClosure(accessibleSet)
		}
	}
	return matchSlc
}

func (this *NfaManager) eClosure(inputStateSet map[*Nfa]struct{}) map[*Nfa]struct{} {
	this.printMatch("accessible", inputStateSet, false)
	stackPtr := MakeStack()
	for inputState, _ := range inputStateSet {
		stackPtr.Push(inputState)
	}
	eClosureSet := make(map[*Nfa]struct{})
	for {
		if stackPtr.IsEmpty() {
			break
		}
		nfaPtr, ok := stackPtr.Pop().(*Nfa)
		if !ok {
			break
		}
		if nfaPtr.edgeSet != nil && len(nfaPtr.edgeSet) == 0 {
			// 空边
			if nfaPtr.upPtr != nil {
				if _, ok := eClosureSet[nfaPtr.upPtr]; !ok {
					eClosureSet[nfaPtr.upPtr] = struct{}{}
					stackPtr.Push(nfaPtr.upPtr)
				}
			}
			if nfaPtr.nextPtr != nil {
				if _, ok := eClosureSet[nfaPtr.nextPtr]; !ok {
					eClosureSet[nfaPtr.nextPtr] = struct{}{}
					stackPtr.Push(nfaPtr.nextPtr)
				}
			}
		}
	}
	this.printMatch(" => ε", eClosureSet, true)
	return eClosureSet
}

func (this *NfaManager) move(eClosureSet map[*Nfa]struct{}, char byte) map[*Nfa]struct{} {
	this.printMatch("match:"+string(char)+" => ε", eClosureSet, false)
	accessibleSet := make(map[*Nfa]struct{})
	for eClosure, _ := range eClosureSet {
		if eClosure.edgeSet != nil && len(eClosure.edgeSet) > 0 {
			if _, ok := eClosure.edgeSet[char]; ok {
				accessibleSet[eClosure.nextPtr] = struct{}{}
			}
		}
	}
	this.printMatch(" => move", accessibleSet, true)
	return accessibleSet
}

func (this *NfaManager) hasAcceptState(accessibleSet map[*Nfa]struct{}) bool {
	if accessibleSet == nil || len(accessibleSet) == 0 {
		return false
	}
	for accessible, _ := range accessibleSet {
		if accessible.nextPtr == nil && accessible.upPtr == nil {
			return true
		}
	}
	return false
}
